import collections
import math
class Solution(object):
    def countPairs(self, nums, k):
        c = collections.defaultdict(int)
        for num in nums:
            c[math.gcd(num, k)] += 1
        d = list(c.keys())
        m = len(d)
        ans = 0
        for i in range(m):
            for j in range(i, m):
                if d[i] * d[j] % k == 0:
                    if i == j:
                        ans += c[d[i]] * (c[d[i]] - 1) // 2
                    else:
                        ans += c[d[i]] * c[d[j]]
        return ans
data = Solution()
nums = [1,2,3,4,5]
k = 2
print(data.countPairs(nums, k))